# 最后一块石头的重量： https://leetcode-cn.com/problems/last-stone-weight/submissions/


# 暴力破解，自己的思路
class Solution:
    def lastStoneWeight(self, stones: list) -> int:
        """
            这道题暴力破解就是每次寻找到最大的两个数，然后比较。 时间复杂度O(n^2)
            1. 首先： x == y 或者是 x < y 都是 使用 y - x，即使得 0 也保留，那么就是说 n个数，比较n-1次就剩下最终的结果了
            2. 寻找第一第二大的数字时，要先将他们赋值为最小值才不会出错，所以需要额外记录最小值
        """
        
        n = len(stones)
        # 寻找最大的数,max_1, max_2 记录对应下标
        max_1 = 0
        max_2 = 0
        # 先算出最小值（下标）
        mi = 0
        for i in range(n):
            if stones[i] < stones[mi]:
                mi = i
        for j in range(n-1):
            # 第一第二大的数，均赋值为最小值
            max_1 = max_2 = mi
            for i in range(n):
                # 注意！！这里必须是 >=, 当例子是[2, 2] 时， max_1, max_2 都是 第一个数，得到错误结果
                if stones[i] == -1: continue
                if stones[i] >= stones[max_1]:   
                    t = max_1
                    max_1 = i
                    max_2 = t
                elif stones[i] > stones[max_2]:
                    max_2 = i
                elif stones[i] >= 0 and stones[i] < stones[mi]:
                    mi = i

            # 我们将对应小的那块石头位置 设置为 -1，代表它消失了
            stones[max_1] -= stones[max_2]
            stones[max_2] = -1
            # 注意： 计算一下 mi 和 max_1 - max_2 之后谁小
            if stones[mi] > stones[max_1]: mi = max_1

        return max(stones)


# 方法2，手写大根堆,时间复杂度为 O(nlogn)
class Solution:
    def lastStoneWeight(self, stones: list) -> int:
        """
            堆排序解决问题： 手写大根堆
        """
        def HeapAdjust(nums, start, end):
            """ 调整堆 """
            rc = nums[start]
            i = start
            while i * 2 + 1 <= end:
                j = i * 2 + 1
                # 判断左右节点哪个大
                if j < end and nums[j] < nums[j + 1]: j += 1
                # 判断是否插入当前位置
                if rc > nums[j]: break
                nums[i] = nums[j]
                i = j

            nums[i] = rc

        def heapify(nums):
            """ 将 列表调整为堆 """
            n = len(nums)
            for i in range((n + 1) // 2 - 1, -1, -1):
                HeapAdjust(nums, i, n - 1)

        def heapPop(nums):
            """ 返回堆顶元素 """
            nums[0], nums[-1] = nums[-1], nums[0]
            HeapAdjust(nums, 0, len(nums) - 2)

            return nums.pop()
            
        # 1. 变为堆
        heapify(stones)
        for i in range(len(stones) - 1):
            # 2. 取最大俩元素
            max_1 = heapPop(stones)
            max_2 = stones[0]
            # 3. 计算结果再保留到 堆顶
            stones[0] = max_1 - max_2
            # 4. 接着调整堆
            HeapAdjust(stones, 0, len(stones)-1)
        
        return stones[-1]


nums = [2, 2]
nums = [3, 7, 8]
s = Solution()
rst = s.lastStoneWeight(nums)
print(rst)

